/*
 * kingdom.cxx
 *
 *  Created on: 1:05:58 PM Oct 15, 2012
 *  Author: Pallab
 *
 * "I have not failed, I have just found 10000 ways that won't work.
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;

#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

inline void wait(double seconds) {
	double endtime = clock() + (seconds * CLOCKS_PER_SEC);
	while (clock() < endtime) {
		;
	}
}
#define T int
inline T fastIn() {
	register char c = 0;
	register T a = 0;
	while (c < 33)
		c = getchar();
	while (c > 33) {
		a = (a * 10) + (c - '0');
		c = getchar();
	}
	return a;
}
const int inf = 1023456789;
const int MX = 16;
int N, E, K;
int Pi[MX];
vector<pair<int, int> > adj[MX];
inline void read() {
	fo(i,MX)adj[i].clear();

	N = fastIn(), E = fastIn(), K = fastIn();
	fo(i,N)
		Pi[i] = fastIn();
	fo(i,E)
	{
		int u = fastIn() - 1, v = fastIn() - 1, c = fastIn();
		adj[u].pb(mk(v, c));
		adj[v].pb(mk(u, c));
	}
}
inline bool is_set(int msk,int i){
	return (msk&(1<<i)) ? true :false ;
}
int dist[MX][MX];
struct info1{
	int u;
	int c;
	info1(int u=0,int c=0):
		u(u),c(c){}
};
inline bool operator<(const info1 &l, const info1 &r){
	return l.c>r.c;
}

inline void apsp(int u){
	priority_queue<info1> pq;
	pq.push(info1(u,0));
	dist[u][u]=0;
	while(!pq.empty()){
		info1 f=pq.top();
		pq.pop();
		foit(it,adj[f.u]){
			int v=it->first,c=it->second+f.c;
			if( c < dist[u][v] ){
				dist[u][v]=c;
				pq.push(info1(v,c));
			}
		}
	}
}
struct info2{
	int p;
	int m;
	int c;
	info2(int p=0, int m=0, int c=0):
		p(p),m(m),c(c){}
};
inline bool operator<(const info2 &l, const info2 &r){
	return l.c > r.c;
}
int fff[1<<MX];
int ppl[1<<MX];
inline int solve(int src){
	priority_queue< info2 > pq;
	pq.push( info2(Pi[src],(1<<src), 0) );
	SET(fff,0);
	fill(ppl,ppl+(1<<MX),inf);
	ppl[1<<src]=0;
	int bst=0;
	while(pq.empty()==false){
		info2 f=pq.top();
		pq.pop();
		if( fff[f.m] )continue;
		fo(i,N){
			if( is_set(f.m,i)==true ){
				fo(j,N){
					if( is_set(f.m,j)==false ){
						int nxt_p = f.p+Pi[j],nxt_m= f.m|(1<<j),nxt_c=f.c+dist[i][j];
						if( nxt_c <=K && fff[nxt_m]==0 && nxt_c < ppl[nxt_m] ){
							ppl[nxt_m]=nxt_c;
							bst=max(nxt_p,bst);
							pq.push( info2(nxt_p,nxt_m,nxt_c) );
						}
					}
				}
			}
		}
		fff[f.m]=1;
	}

	return bst;
}
inline void proc() {
	fo(i,MX)
		fill(dist[i],dist[i]+MX, inf);

	fo(i,N)
			apsp(i);
	/*fo(i,N){
		fo(j,N)cout<<dist[i][j]<<' ';
		line;
	}
	puts("---------");*/
	cout << solve(0) << '\n';
}
int main() {
	int kase = 1;
#if defined( xerxes_pc )
	if (!freopen("in", "r", stdin))
		puts("error opening file kingdom/in1 "), assert(0);
	kase = 1;
#endif
	kase = fastIn();
	fo(i,kase)
	{
		read();
		proc();
	}
	return 0;
}

